//496.下一个更大元素1
//https://leetcode.cn/problems/next-greater-element-i/
class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        int n1 = nums1.size(), n2 = nums2.size();
        unordered_map<int,int> hash;
        stack<int> st; //单调栈
        vector<int> ret(n1,-1);
        for(int i = n2-1;i>=0;--i)
        {
            //比当前数大的数会留在栈中
            while(!st.empty() && nums2[i]>=st.top()) st.pop(); //排除比当前数小的数
            hash[nums2[i]] = st.empty()?-1:st.top();
            st.push(nums2[i]);
        }
        for(int i = 0;i<n1;++i) if(hash.count(nums1[i])) ret[i] = hash[nums1[i]];
        return ret;
    }
};